Generate Parentheses
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
Given a number n, build every distinct string you can make using exactly n open-parenthesis characters and n close-parenthesis characters, so that the parentheses always pair up correctly. A string pairs up correctly when every close parenthesis matches an already-open one, and no parenthesis is left unmatched at the end.
Return all of these strings. The order does not matter.
Input: n = 1
Output: ["()"]
There's only one way to pair up a single open and close parenthesis.
Input: n = 2
Output: ["(())", "()()"]
With 2 pairs, you can either nest one pair inside the other, or place them side by side.
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
With 3 pairs, there are 5 ways to arrange them correctly.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.